package interview.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * Created by yzy on 2021-02-20 15:27
 */
public class MergeIntervals {

    /**
     * 3ms, 98.75%
     *
     * @param intervals
     * @return
     */
    public int[][] merge_two(int[][] intervals) {
        int[] start = new int[intervals.length];
        int[] end = new int[intervals.length];

        for(int i=0; i<intervals.length; i++){
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }

        Arrays.sort(start);
        Arrays.sort(end);
        List<int[]> resList = new ArrayList<>();
        int s = start[0];
        for(int i=0; i<end.length; i++){
            if(i == end.length-1){
                resList.add(new int[]{s,end[i]});
            }
            if(i<end.length-1 && end[i] < start[i+1]){
                resList.add(new int[]{s, end[i]});
                s = start[i+1];
            }
        }

        int[][] resArr = new int[resList.size()][];
        int idx=0;
        for(int[] tmp : resList){
            resArr[idx++] = tmp;
        }
        return resArr;
    }

        /**
         * 数组不一定是完全正序排序的，所以不能够从左到右顺序处理
         * @param intervals
         * @return
         */
    public int[][] merge(int[][] intervals) {
        // 按interval第一个元素排序
        Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));
        List<int[]> resList = new ArrayList<>();

        int start = intervals[0][0];
        int end = intervals[0][1];
        for(int i=1; i<intervals.length; i++){
            int[] curr = intervals[i];
            if(curr[0] > end){
                resList.add(new int[]{start,end});
                start = curr[0];
                end = curr[1];
            }else{
                end = end > curr[1] ? end : curr[1];
            }
        }
        // 把最后的一个再加上
        resList.add(new int[]{start, end});

        int[][] resArr = new int[resList.size()][];
        int idx=0;
        for(int[] tmp : resList){
            resArr[idx++] = tmp;
        }
        return resArr;
    }
}
